package binary_tree;

/**
 * 基础二叉树
 */
public class MyBinTree {//节点的创建
    private static class TreeNode{
        char val;
        //左子树根节点
        TreeNode left;
        //右子树根节点
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public static TreeNode build(){
        TreeNode nodeA=new TreeNode('A');
        TreeNode nodeB=new TreeNode('B');
        TreeNode nodeC=new TreeNode('C');
        TreeNode nodeD=new TreeNode('D');
        TreeNode nodeE=new TreeNode('E');
        TreeNode nodeF=new TreeNode('F');
        TreeNode nodeG=new TreeNode('G');
        TreeNode nodeH=new TreeNode('H');
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeE.right=nodeH;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        return nodeA;
    }

    /**
     * 先序遍历：根左右
     * 传入一棵二叉树的根节点，就可以按照先序遍历的方式来输出节点值
     * @param root
     */
    public static void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        System.out.print(root.val+"  ");
        //按照先序遍历的方式递归的访问左树
        preOrder(root.left);
        //按照先序遍历的方式递归的访问右树
        preOrder(root.right);
    }

    /**
     * 中序遍历 ：左根右
     * 传入一棵二叉树的根节点，就可以按照中序遍历的方式来输出节点值
     * @param root
     */
    public static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        //按照中序遍历的方式递归的访问左树
        inOrder(root.left);
        System.out.print(root.val+"  ");
        //按照中序遍历的方式递归的访问右树
        inOrder(root.right);
    }

    /**
     * 后序遍历：左右根
     * 传入一棵二叉树的根节点，就可以递归访问左子树，再递归访问右子树
     * @param root
     */
    public static void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        //按照中序遍历的方式递归的访问左树
        postOrder(root.left);
        //按照中序遍历的方式递归的访问右树
        postOrder(root.right);
        System.out.print(root.val+"  ");
    }

    /**
     * 传入一棵二叉树就能够统计出二叉树中一共有多少个根节点
     * @param root
     * @return
     */
    public static int getNodes(TreeNode root){
        //边界条件
        if (root==null){
            return 0;
        }
        //整棵树的节点数=根节点+左子树节点数+右子树节点数；
        return getNodes(root.left)+getNodes(root.right)+1;
    }

    /**
     * 传入一棵二叉树就能够统计二叉树中一共有多少个叶子结点
     * @param root
     * @return
     */
    public static int getLeafNodes(TreeNode root){
        if(root==null){
            return 0;
        }
        //当前树肯定不为空，返回左子树的叶子结点+右子树的叶子结点
        return getNodes(root.left)+getNodes(root.right);
    }

    /**
     * 传入一棵树，计算该树的高度
     * @param root
     * @return
     */
    public static int height(TreeNode root){
        if(root==null){
            return 0;
        }
        //当前树不为空，返回左子树和右子树的较大值+根（第一层）
        return 1+Math.max(height(root.left),height(root.right));
    }


    public static boolean contains(TreeNode root,char value){
        if (root==null){
            return false;
        }
        if (root.val==value){
            return true;
        }
        return contains(root.left,value)||contains(root.right,value);
    }

    /**
     * 计算第k层的节点个数
     * @param root
     * @param k
     * @return
     */
    public static int getKLevelNodes(TreeNode root,int k){
        if(null==null||k<=0){
            return 0;
        }
        //二叉树不为空，且k>=2
        //root为根节点的第三层=root.left的k-1层+root.right的k-1层
        return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);
    }

    public static void main(String[] args) {
        TreeNode root=build();
        System.out.println("前序遍历的结果：");
        preOrder(root);
        System.out.println(" ");
        inOrder(root);
        System.out.println(" ");
        postOrder(root);
        System.out.println(" ");
        System.out.println("当前一定有"+getNodes(root)+"根节点");
        System.out.println("当前树有"+getLeafNodes(root)+"叶子结点");
        System.out.println("当前树是否包含value:"+contains(root,'E'));
        System.out.println("该二叉树的高度："+height(root));
        System.out.println("第三层的节点个数:"+getKLevelNodes(root,3));
    }
}

